package 力扣日常刷题.木23一月.第16天316;

import 力扣日常刷题.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 帅小伙
 * @date 2022/3/16
 * @description
 */
public class Demo85从前序与中序遍历序列构造二叉树 {


/*    public static void main(String[] args) {
        Demo85从前序与中序遍历序列构造二叉树 demo = new Demo85从前序与中序遍历序列构造二叉树();

        demo.buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7});
    }*/

    int[] preorder;
    Map<Integer,Integer> dic = new HashMap<>();
    /*
    * preorder  先序
    * inorder   中序
    * */
    public TreeNode buildTree(int[] preorder,int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            dic.put(inorder[i],i);
        }
        return recur(0,0,inorder.length - 1);
    }

    public TreeNode recur(int root,int left,int right) {
        if(left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        // 获得中序的位置   前面是左节点  后面是右节点
        int i = dic.get(preorder[root]);
        node.left = recur(root + 1,left,i - 1);
        node.right = recur(root + i - left + 1,i + 1,right);
        return node;
    }
}
